#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
#define endl '\n'
const int N = 5010;
const int INF = 0x3f3f3f3f;
int a[N];
int G[N + 1][N + 1];
 
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

void solve() 
{
    int g = 0;
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        g = gcd(g, a[i]);
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++) 
        if(a[i] == g) 
            cnt++;
    if(cnt) cout << n - cnt << endl;
    else 
    {
        vector<int> dp(N + 1, INF);
        dp[0] = 0;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j <= N; j++)
            {
                int y = G[a[i]][j];
                dp[y] = min(dp[y], dp[j] + 1);
            }
        }
        cout << dp[g] + n - 2 << endl;
    }
 }

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
	cin >> T;
    for(int i = 0; i <= N; i++)
    {
        for(int j = 0; j <= N; j++)
        {
            G[i][j] = gcd(i, j);
        }
    }
	while(T--)
	{
        solve();
	}
	return 0;
}